package com.wuyou.mid;

import java.util.Arrays;

/**
 * 53. 最大子数组和
 */
public class MaxSubArray {

    public static void main(String[] args) {
//        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        int[] nums = {1};
//        int[] nums = {8, -19, 5, -4, 20};
        int[] nums = {1, 2, -1, -2, 2, 1, -2, 1, 4, -5, 4};
        System.out.println(solution_2(nums));
    }

    public static int solution_2(int[] nums) {
        int sum = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum > 0) {
                sum += nums[i];
            }else {
                sum = nums[i];
            }
            res = Math.max(sum, res);
        }
        return res;
    }

    public static int solution_1(int[] nums) {
        int left = 0, right = 0, maxSubSum = -1, max = Arrays.stream(nums).max().getAsInt();
        int tempSum = max >= 0 ? 0 : max;
        while (right < nums.length) {
            tempSum += nums[right++];
            if (tempSum < 0) {
                while (left < right) {
                    tempSum -= nums[left++];
                    if (tempSum > 0) break;
                }
            }
            maxSubSum = Math.max(maxSubSum, tempSum);
        }
        if (max < 0) {
            return max;
        } else {
            return maxSubSum;
        }
    }
}
